// https://leetcode.cn/problems/reverse-nodes-in-k-group/
// 
// 题干：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
//      k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
//      你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换


// 示例：
// 输入：head = [1,2,3,4,5], k = 3     输出：[3,2,1,4,5]


// 碎语：画图！！

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        for (auto p = dummy; ; )
        {
            auto q = p;
            for (int i = 0; i < k && q; i++) q = q->next;
            if (q == nullptr) break;

            auto a = p->next, b = a->next;
            for (int i = 0; i < k - 1; i++)
            {
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }
            auto c = p->next;
            p->next = a, c->next = b;
            p = c;
        }

        return dummy->next;
    }
};

int main()
{
    auto dummy = new ListNode(-1), cur = dummy;
    for (int i = 1; i <= 5; i++)
    {
        cur->next = new ListNode(i);
        cur = cur->next;
    }

    auto rhead = Solution().reverseKGroup(dummy->next, 3);

    while (rhead)
    {
        cout << rhead->val << " ";
        rhead = rhead->next;
    }
    cout << endl;

    return 0;
}